package problems.daily.y2021m6;

import java.util.HashMap;
import java.util.Map;

/**
 * @author habitplus
 * @since 2021-06-24 10:11
 */
public class T20210624N1 {
    // 149. 直线上最多的点数
    // 给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。
    public int maxPoints(int[][] points) {
        // hash表 + 循环 + 优化
        int len = points == null ? 0 : points.length;
        if (len <= 2) {
            return len;
        }
        int res = 0;
        for (int i = 0; i < len - 1; i++) {
            // 存放每个相同斜率直线上的点数，这里应为是整除原因，所以采用分数存储斜率，即 "a#b" 相当于【a/b 的最简分式】
            Map<String, Integer> xieLvMap = new HashMap<>();
            // 计算经过第 i 个点的所有直线上的点
            for (int j = i + 1; j < len; j++) {
                int dx = points[i][0] - points[j][0];
                int dy = points[i][1] - points[j][1];
                String key = "";
                if (dx == 0) {
                    // 斜率为无穷大
                    key = "0#0";
                } else if (dy == 0) {
                    // 斜率为零
                    key = "0";
                } else {
                    // 判断结果是否为负数
                    if((dx > 0 && dy < 0) || (dx < 0 && dy > 0)) {
                        // 异号，结果为负数
                        key = "-";
                    }
                    // 辗转相除法：求 dx 与 dy 的最大公约数，用于化简分式
                    dx = Math.abs(dx);
                    dy = Math.abs(dy);
                    int g = gcd(dx, dy);
                    dx /= g;
                    dy /= g;
                    key += String.format("%d#%d", dy, dx);
                }
                xieLvMap.put(key, xieLvMap.getOrDefault(key, 1) + 1);
            }

            int maxNum = 0;
            for (Map.Entry<String, Integer> en : xieLvMap.entrySet()) {
                int v = en.getValue();
                maxNum = Math.max(v, maxNum);
            }
            res = Math.max(maxNum, res);
        }
        return res;
    }

    /**
     * 辗转相除法求最大公因数
     */
    private int gcd(int a, int b) {
        return b != 0 ? gcd(b, a % b) : a;
    }

    public static void main(String[] args) {
        System.out.println(new T20210624N1().maxPoints(new int[][]{{1,1}, {3,2}, {5,3}, {4,1}, {2,3}, {1,4}}));
    }
}
